#include <stdio.h>
void Swap(int *p1,int*p2)
{
	int tmp=*p1;
	*p1=*p2;
	*p2=tmp;
	
}
void Print(int*a,int n)
{
	for(int i=0;i<n;i++)
		{
			printf("%d ",a[i]);
		}
	printf("\n");
}
void ShellSort(int* a, int n) {
	int gap = n;//步距
	while(gap>0)
		{
			gap=(gap+1)/3;//步距
			for (int i = 0; i < n - gap; i++) {
				int began = i;
				int end = began + gap;
				while (began >= 0)
					{
						if (a[began] > a[end])
							{
								began = began - gap;
							}
						else
							{
								break;
							}
					}
				
				Swap(&a[began + gap], &a[end]);
				
			}
		}
	
}

int main(int argc, char *argv[]) 
{
	int arr[]={54,38,96,23,15,72,60,45,83};
	Print(arr,sizeof(arr)/sizeof(arr[0]));
	ShellSort(arr, sizeof(arr)/sizeof(arr[0]));
	Print(arr,sizeof(arr)/sizeof(arr[0]));

}